package pfq.demo.algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序:
 * <p>
 * 每次以中间的元素为轴心，高低各一个索引，低索引向右移动，直到找到比轴心元素大的为止，
 * 高索引向左移动，直到找到比轴心元素小的为止，
 * 两者交换数据后继续向中间靠拢，直到低索引不小于高索引为止，这样以该中间元素为轴心的排序就结束了
 * 接下来分别对该轴心元素的左边和右边分别进行递归，直到结束为止
 * <p>
 * 时间复杂度
 * 最好：O(nlog2n)
 * 最坏：O(n^2)
 * 平均：O(nlog2n)
 */
public class QuickSort {

    public static void main(String[] args) {

        int[] data = Arrays.copyOf(Utils.data(), Utils.data().length);
        System.out.println("排序前：" + Arrays.toString(data));
        quickSort(data, 0, data.length - 1);
//        quickSort2(data);
        System.out.println("排序后：" + Arrays.toString(data));

    }

    /**
     * 快速排序
     *
     * @param arr 待排序的数组
     */
    public static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        int middleValue;
        int leftTempIndex;
        int rightTempIndex;
        if (leftIndex < rightIndex) {
            // 取出中间的轴心元素
            middleValue = arr[(leftIndex + rightIndex) / 2];
            leftTempIndex = leftIndex - 1;
            rightTempIndex = rightIndex + 1;
            while (true) {
                while (arr[++leftTempIndex] < middleValue) ;
                while (arr[--rightTempIndex] > middleValue) ;
                if (leftTempIndex >= rightTempIndex) {
                    break;
                }
                Utils.swap(arr, leftTempIndex, rightTempIndex);
            }

            quickSort(arr, leftIndex, leftTempIndex - 1);
            quickSort(arr, rightTempIndex + 1, rightIndex);
        }

    }

    /**
     * 快速排序
     * <p>
     * 整体思路：
     * 1. 每次随机取数组中的一个元素作为分区点（pivot，一般取数组中最后一位）
     * 2. 遍历数组，与pivot元素进行比较，筛选出比pivot小的放在pivot的前面，比pivot大的放在pivot的后面，一次遍历可以得到pivot的的正确位置，以及比pivot小的区间和比pivot大的区间
     * 3. 继续将两个区间分别进行1和2的操作直到所有数据完成排序
     * 关键在于2
     * <p>
     * 代码思路：（快慢指针）
     * 1. 每次取区间最后一个元素作为pivot
     * 2. 两个指针同时指向区间的第一个元素
     * 3. 第一个指针向后遍历直到找到比pivot小的元素，然后和第二个指针指向的元素进行交换
     * 4. 接着第二个指针+1，第一个指针继续向后寻找比pivot小的元素，继续第3步操作，直到元素遍历结束
     * 5. 最后把第二个指针指向的位置和最后一个元素也就是pivot进行交换即可
     * <p>
     * 这个思路，其实和高低指针一样，高指针找到比pivot小的元素，低指针找到比pivot大的元素，然后进行交换
     * 这个的话是，第一个指针找到比pivot小的元素，然后和第二个元素进行交换，接着第二个指针+1，其实这里的第二个指针指向的就是比pivot大的元素，因为小的元素已经被第一个指针提前指向了，第二个指针在第一个指针后面，指向的只能是比pivot大的元素
     */
    public static void quickSort2(int[] a) {
        if (a == null || a.length == 1) {
            return;
        }

        quickSort2_(a, 0, a.length - 1);
    }

    private static void quickSort2_(int[] a, int p, int r) {

        if (p >= r) {
            return;
        }
        int q = findPivot(a, p, r);
        quickSort2_(a, p, q - 1);
        quickSort2_(a, q + 1, r);

    }

    private static int findPivot(int[] a, int p, int r) {

        int pivot = a[r];
        int j = p;
        for (int i = p; i <= r - 1; i++) {
            if (a[i] < pivot) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                j++;
            }
        }

        a[r] = a[j];
        a[j] = pivot;

        return j;
    }


}
